Error-correcting codes can be used for carrying message data over a noisy channel. Such codes have built-in patterning, parity checks, and/or redundancy. If the noise is not too great, then corrupted codewords in the received signal can be repaired to recover the original message data, sometimes with guaranteed reliability. There is a theoretical limit to the amount of corruption that can be reversed. Codes constrained to output a single unique codeword for each input message word can typically correct up to d/2 errors, where d is the “minimum distance” of the code, i.e., such that any two encodings of two different messages differ in at least d positions. For example, some error-correcting codes might unambiguously recover up to 25% of errors in trying to decode the original message word.
List-decoding, on the other hand, compares the received corrupted codeword with codewords from within a radius of similarity. The degree of similarity for searching for potential matches among the known codewords is referred to as the “Hamming distance.” List-decoding allows recovery from noise levels significantly higher than the noise levels allowing unique decoding, and is therefore used when the noise level is so high that unambiguous decoding is not possible. Theoretically such binary codes can correct up to nearly 50% of the errors of a corrupted codeword. List decoding has attracted a lot of attention in the literature.
Reed-Solomon codes are widely used. They are block-based error-correcting codes that are based on a technique of evaluating polynomials at selected points in a finite field where the polynomials are constructed from the original message data. The number of such evaluations are more than would be strictly necessary to reconstruct the polynomial under ideal conditions from some of its samples, this oversampling allows the polynomial to be recovered correctly even if (not too many) samples become corrupted from noise in the transmission channel. Reed-Solomon codes are often used in compact disc (CD) and DVD technology.
McEliece type cryptosystems use asymmetric key paradigms, but in pure form have never gained wide use due to some inherent disadvantages when compared with the systems in wide use. The algorithms use Goppa codes, a type of error-correcting code. Goppa codes are relatively easy to decode, but distinguishing them from a random linear code is considered difficult—this indistinguishability forms the basis of their use in McEliece cryptosystems, since decoding random linear codes is believed to be hard. The keys created can be a public and private key pair of the public key infrastructure (PKI). The usual disadvantage is that the private and public keys are large matrices. A public key can be very large. There have been some partial attempts to cryptanalyze McEliece systems, but none have been successful. However, the pure algorithm is rarely used in conventional practice because of the relatively large keys and because the ciphertext is twice as large, with respect to conventional parameters, as the plaintext.
Nonetheless, a McEliece system typically consists of three parts: probabilistic key generation steps that produce a public and a private key; probabilistic encryption steps; and deterministic decryption steps.
Users in a McEliece implementation thus share a set of common security parameters: message length k, codeword length n, and number of errors that can be corrected t. Conventional values for these parameters are k=644; n=1024, and t=38. During McEliece key generation:                Users select a binary (n, k)-linear code C capable of correcting t errors. This code usually possesses an efficient decoding algorithm.        User “Alice” generates a k×n generator matrix G for the code C.        The generator selects a random k×k binary non-singular matrix S.        The generator selects a random n×n permutation matrix P.        The generator computes the k×n matrix Ĝ=SGP.        Alice's public key is (Ĝ,t); her private key is (S, G, P).        
For message encryption, when “Bob” wishes to send a message m to Alice whose public key is (Ĝ,t):                The encoder encodes the message which is a binary string of length k.        The encoder computes the vector c′=mĜ.        The encoder generates a random n-bit vector z containing at most t ones.        The encoder computes the ciphertext as c=c′+z.        
For message decryption:                The decoder computes the inverse of P, that is, P−1,        The decoder computes ĉ=cP−1.        The decoder uses the decoding algorithm for the code C to decode ĉ to {circumflex over (m)}.        The decoder computes message m={circumflex over (m)}S−1.        
The McEliece type cryptosystems are even more impractical for small devices with very low power because one must expend more computing resources on decoding and encoding over finite fields than would be needed for more popular coding algorithms such as low density parity check codes and Turbo codes.